package com.tree;

import java.util.*;

public class test {
    public int widthOfBinaryTree(TreeNode root) {

        if(root==null){
            return 0;
        }

        Deque<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.offer(root);
        root.val=1;
        int leng=0;
       while (!treeNodes.isEmpty()){
            int size = treeNodes.size();
            int pre=treeNodes.peekLast().val-treeNodes.pollFirst().val+1;
             leng=Math.max(leng,pre);
            for (int i = 0; i < size; i++) {
                TreeNode node = treeNodes.poll();
                int pos = node.val;
                if (node.left!=null){
                    node.left.val=2*pos;
                    treeNodes.offer(node.left);
                }
                if (node.right!=null){
                    node.right.val=2*pos+1;
                    treeNodes.offer(node.right);
                }
            }
        }
        return leng;
    }
    //给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    //
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if (p==null&&q==null)
            return true;
        if (p==null||q==null)
            return false;
        if (p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //给定一个二叉树，检查它是否是镜像对称的。
    public boolean isSymmetric(TreeNode root) {

       if (root==null)
           return true;
       return isMirror(root,root);
    }
    public boolean isMirror(TreeNode t1, TreeNode t2){
        if (t1==null&&t2==null)
            return true;
        if (t1==null||t2==null)
            return false;
        return (t1.val==t2.val)&&isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
    }
   // 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        Deque<TreeNode> deque =  new ArrayDeque();
        if (root!=null){
            deque.add(root);
        }

        while (!deque.isEmpty()){
            ArrayList<Integer> level = new ArrayList<>();
            int n=deque.size();

            for (int i = 0; i < n; i++) {
                TreeNode poll = deque.poll();
                level.add(poll.val);
                if (poll.left!=null)
                    deque.add(poll.left);
                if (poll.right!=null)
                    deque.add(poll.right);
            }
            lists.add(level);
        }
        return lists;



    }
}
